home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / vsc92nov.zip / storage.c < prev    next >
C/C++ Source or Header  |  1992-11-02  |  19KB  |  860 lines
  1. /*
  2.  * storage.c -- Implementation of a storage allocation scheme with
  3.  *              stop-and-copy-based garbage collection
  4.  *
  5.  * (C) m.b (Matthias Blume), Wed Jun  3 15:12:45 MET DST 1992, HUB/Ger
  6.  *         Humboldt-University of Berlin, Germany
  7.  */
  8.  
  9. # ident "@(#)storage.c    (C) M.Blume, Humboldt-Uni Berlin, 1.9"
  10.  
  11. # include "align.h"
  12. # include "storage.h"
  13. # include "storage-t.h"
  14. # include "except.h"
  15.  
  16. # include <stdio.h>
  17. # include <stdlib.h>
  18. # include <memory.h>
  19. # include <assert.h>
  20. # include <string.h>
  21.  
  22. # define GVA_SIZE_INCR 32    /* propably never needed more than once */
  23.  
  24. # define NULL_IDENTIFIER        253
  25. # define MARK_IDENTIFIER        254
  26. # define REFERTO_IDENTIFIER        255
  27.  
  28. struct broken_heart {
  29.     object_descriptor _;
  30.     void *new_location;
  31. };
  32.  
  33. /* fake object description for broken hearts */
  34. static
  35. struct object_description broken_heart_description = {
  36.     0,
  37.     sizeof (struct broken_heart),
  38.     NULL,
  39.     NULL,
  40.     0,
  41.     &broken_heart_description,
  42.     NULL, NULL, NULL,
  43.     NULL, NULL, NULL,
  44.     NULL
  45. };
  46.  
  47. /*
  48.  * Determining the type of an object
  49.  */
  50.  
  51. # ifdef SCMTYPEOF_FUNC
  52. object_descriptor ScmTypeOf (void *obj)
  53. {
  54.   return obj == NULL ? NULL : ((struct broken_heart *)obj)->_;
  55. }
  56. # endif
  57.  
  58. /* indicator of running gc */
  59. static
  60. int gc_running = 0;
  61.  
  62. /* rubber band array of global variable's locations: */
  63. static
  64. size_t gva_length, gva_firstfree;
  65. static
  66. struct gva {
  67.   void *location;
  68.   perform_on_subs_proc for_each_sub;
  69. } *gva = NULL;
  70.  
  71. int register_global_object (void *location, perform_on_subs_proc proc)
  72. {
  73.   if (gva == NULL) {
  74.     if ((gva = (struct gva *) malloc (sizeof (struct gva) * GVA_SIZE_INCR))
  75.     == NULL)
  76.       return -1;
  77.     gva_length = GVA_SIZE_INCR;
  78.     gva_firstfree = 0;
  79.   } else if (gva_firstfree >= gva_length) {
  80.     struct gva *tmp;
  81.     if ((tmp =  (struct gva *)
  82.      realloc (gva, sizeof (struct gva)
  83.           * (GVA_SIZE_INCR + gva_length)))
  84.     == NULL)
  85.       return -1;
  86.     gva = tmp;
  87.     gva_length += GVA_SIZE_INCR;
  88.   }
  89.   gva [gva_firstfree].location = location;
  90.   gva [gva_firstfree].for_each_sub = proc;
  91.   gva_firstfree++;
  92.  
  93.   return 0;
  94. }
  95.  
  96. struct heap_block {
  97.   size_t size;            /* total length of array */
  98.   size_t firstfree;        /* first free position in array */
  99.   size_t next_copied;        /* used during gc */
  100.   align_t array[1];        /* itself */
  101. };
  102.  
  103. struct heap {
  104.   size_t size;            /* total number of heap block entries */
  105.   size_t firstfree;        /* number of allocated heap blocks */
  106.   size_t search_start;        /* start search for free space here */
  107.   size_t next_copied;        /* used during gc */
  108.   struct heap_block **array;
  109.   size_t total_size;
  110.   size_t total_used;
  111. };
  112.  
  113. static
  114. struct heap heap = {
  115.   0,
  116.   0,
  117.   0,
  118.   0,
  119.   NULL,
  120.   0,
  121.   0
  122. };
  123.  
  124. static struct heap passive_heap = {
  125.   0,
  126.   0,
  127.   0,
  128.   0,
  129.   NULL,
  130.   0,
  131.   0
  132. };
  133.  
  134. static size_t min_heap_size = MIN_HEAP_SIZE;
  135.  
  136. static
  137. size_t index_of_satisfying_heap_block (size_t elem)
  138. {
  139.   size_t i;
  140.  
  141.   for (i = heap.search_start; i < heap.firstfree; i++)
  142.     if (elem <= heap.array[i]->size - heap.array[i]->firstfree)
  143.       break;
  144.  
  145.   return i;
  146. }
  147.  
  148. static
  149. size_t index_of_new_heap_block (size_t elem)
  150. {
  151.   size_t size;
  152.   struct heap_block *block;
  153.   struct heap_block **tmp;
  154.  
  155. # ifdef DEBUG
  156.   fprintf (stderr, "DEBUG: allocating new heap block (elem = %d)\n", elem);
  157. # endif
  158.  
  159.   size = (elem > HEAP_BLOCK_SIZE) ? elem : HEAP_BLOCK_SIZE;
  160.  
  161.   if (heap.array == NULL) {
  162.     if ((heap.array = (struct heap_block **)
  163.      malloc (HEAP_SIZE_INCR * sizeof (struct heap_block *)))
  164.     == NULL)
  165.       return (size_t) -1;
  166.     heap.size = HEAP_SIZE_INCR;
  167.     heap.firstfree = heap.search_start = 0;
  168.   } else if (heap.firstfree >= heap.size) {
  169.     if ((tmp = (struct heap_block **)
  170.      realloc (heap.array,
  171.           (heap.size + HEAP_SIZE_INCR) * sizeof (struct heap_block *)))
  172.     == NULL)
  173.       return (size_t) -1;
  174.     heap.array = tmp;
  175.     heap.size += HEAP_SIZE_INCR;
  176.   }
  177.  
  178.   if ((block = (struct heap_block *)
  179.        malloc (sizeof (struct heap_block) +
  180.            sizeof (align_t) * (size - 1)))
  181.       == NULL)
  182.     return (size_t) -1;
  183.  
  184.   heap.total_size += size;
  185.  
  186.   block->size = size;
  187.   block->firstfree = block->next_copied = 0;
  188.  
  189.   heap.array [heap.firstfree] = block;
  190.   return heap.firstfree++;
  191. }
  192.  
  193. /* forward declaration of gc_getbytes */
  194. static
  195. void *gc_getbytes (size_t bytes);
  196.  
  197. /*ARGSUSED*/
  198. static
  199. void update_address (void **location, void *ignore)
  200. {
  201.   struct broken_heart *obj;
  202.   void *new_location;
  203.   size_t size;
  204.   size_hook_proc shp;
  205.  
  206.   if ((obj = (struct broken_heart *) *location) == NULL) {
  207.     return;
  208.   }
  209.  
  210.   if (obj->_ == &broken_heart_description) {
  211.     *location = obj->new_location;
  212.   } else {
  213.     if ((size = obj->_->size) == 0) {
  214.       if ((shp = obj->_->size_hook) == NULL)    /* constant non-heap object */
  215.     return;                    /* don't move it ! */
  216.       else
  217.     size = (* shp) (obj);
  218.     }
  219.     /* relies on having gc_running set!!! */
  220.     new_location = gc_getbytes (size);
  221.     memcpy (new_location, (void *) obj, size);
  222.     obj->new_location = *location = new_location;
  223.     obj->_ = &broken_heart_description;
  224.   }
  225. }
  226.  
  227. static
  228. int cmp_heap_block_size (const void *vx1, const void *vx2)
  229. {
  230.   size_t s1, s2;
  231.  
  232.   s1 = (*(struct heap_block **)vx1)->size;
  233.   s2 = (*(struct heap_block **)vx2)->size;
  234.  
  235.   if (s1 < s2)
  236.     return -1;
  237.   if (s1 == s2)
  238.     return 0;
  239.   return 1;
  240. }
  241.  
  242. static
  243. void *next_moved_object (void)
  244. {
  245.   struct heap_block *hb = NULL;
  246.   struct broken_heart *res;
  247.   size_t size, i;
  248.  
  249.   while (heap.next_copied < heap.search_start &&
  250.      heap.array [heap.next_copied]->next_copied >=
  251.      heap.array [heap.next_copied]->firstfree)
  252.     heap.next_copied++;
  253.  
  254.   for (i = heap.next_copied; i < heap.firstfree; i++) {
  255.     hb = heap.array [i];
  256.     if (hb->next_copied < hb->firstfree)
  257.       break;
  258.   }
  259.   if (i == heap.firstfree)
  260.     return NULL;
  261.  
  262.   res = (void *) (hb->array + hb->next_copied);
  263.   if ((size = res->_->size) == 0)
  264.     size = (* res->_->size_hook) (res);
  265.  
  266.   hb->next_copied += (size + sizeof (align_t) - 1) / sizeof (align_t);
  267.  
  268.   return res;
  269. }
  270.  
  271. # define PRE_GC        1
  272. # define POST_GC    2
  273. # define MODULE_INIT    3
  274.  
  275. static
  276. void all_modules (int what)
  277. {
  278.   unsigned i;
  279.   module_proc mip;
  280.  
  281.   for (i = 0; i < identifier_map_length; i++) {
  282.     switch (what) {
  283.     case PRE_GC:
  284.       mip = identifier_map[i]->pre_gc_action;
  285.       break;
  286.     case POST_GC:
  287.       mip = identifier_map[i]->post_gc_action;
  288.       break;
  289.     default: /* MODULE_INIT */
  290.       mip = identifier_map[i]->module_init;
  291.       break;
  292.     }
  293.     if (mip != NULL)
  294.       (* mip) ();
  295.   }
  296. }
  297.  
  298. static
  299. void sort (void *array, size_t len, size_t siz,
  300.         int (* cmp) (const void *, const void *))
  301. {
  302.   qsort (array, len, siz, cmp);
  303. }
  304.  
  305. static align_t dummy_cache_buf [1];
  306. static align_t *cached_heap_top = dummy_cache_buf;
  307. static align_t *cached_heap_end = dummy_cache_buf;
  308. static size_t cached_block_no = 0;
  309.  
  310. static
  311. void exchange_heaps (void)
  312. {
  313.   struct heap tmp;
  314.   size_t i;
  315.  
  316.   /* swap heaps */
  317.   tmp = passive_heap;
  318.   passive_heap = heap;
  319.   heap = tmp;
  320.  
  321.   /* Sort entries of new heap */
  322.   if (heap.array != NULL && heap.firstfree > 0)
  323.     sort (heap.array,
  324.        heap.firstfree,
  325.        sizeof (struct heap_block *),
  326.        cmp_heap_block_size);
  327.  
  328.   /* reset all firstfree- and next_copied-members */
  329.   for (i = 0; i < heap.firstfree; i++)
  330.     heap.array[i]->firstfree =
  331.       heap.array[i]->next_copied = 0;
  332.   heap.search_start = heap.next_copied = heap.total_used = 0;
  333.  
  334.   /* reset cache */
  335.   cached_heap_top = cached_heap_end = dummy_cache_buf;
  336. }
  337.  
  338. static size_t getbytes_count = 0;
  339. static clock_t gc_clock_accu = 0;
  340.  
  341. clock_t total_gc_clock (void)
  342. {
  343.   return gc_clock_accu;
  344. }
  345.  
  346. static
  347. void garbage_collection (void)
  348. {
  349.   size_t i;
  350.   struct broken_heart *next;
  351.   perform_on_subs_proc fesp;
  352.   size_t pre_gc_gbc = getbytes_count;
  353.   clock_t tmp_clock;
  354.  
  355. # ifdef DEBUG
  356.   fputs ("DEBUG: Collecting ...", stderr);
  357. # endif
  358.  
  359.   /* mark gc as being running */
  360.   announce_gc_start ();
  361.   gc_running = 1;
  362.  
  363.   tmp_clock = clock ();
  364.  
  365.   all_modules (PRE_GC);
  366.  
  367.   exchange_heaps ();
  368.  
  369.   /* run update_address on global locations */
  370.   for (i = 0; i < gva_firstfree; i++)
  371.     if ((fesp = gva [i].for_each_sub) != NULL)
  372.       (* fesp) (gva [i].location, update_address, NULL);
  373.     else
  374.       update_address (gva [i].location, NULL);
  375.  
  376.   /* just do it! */
  377.   while (next = next_moved_object ())
  378.     if ((fesp = next->_->for_each_sub) != NULL)
  379.       (* fesp) (next, update_address, NULL);
  380.  
  381.   all_modules (POST_GC);
  382.  
  383.   tmp_clock = clock () - tmp_clock;
  384.   gc_clock_accu += tmp_clock;
  385.  
  386.   /* reset gc_running flag */
  387.   gc_running = 0;
  388.   announce_gc_end ();
  389.  
  390.   gc_statistics_proc (
  391.     pre_gc_gbc, getbytes_count - pre_gc_gbc,
  392.     min_heap_size, heap.total_size, heap.total_used,
  393.     tmp_clock);
  394.  
  395.   getbytes_count = 0;
  396.  
  397. # ifdef DEBUG
  398.   fputs (" done\n", stderr);
  399. # endif
  400. }
  401.  
  402. void gc_set_min_heap_size (size_t bound)
  403. {
  404.   min_heap_size = bound;
  405. }
  406.  
  407. static
  408. void *gc_getbytes (size_t bytes)
  409. {
  410.   size_t elem = (bytes + sizeof (align_t) - 1) / sizeof (align_t);
  411.   size_t i;
  412.   struct heap_block *hb;
  413.   void *ret;
  414.  
  415.   getbytes_count++;
  416.   if ((i = index_of_satisfying_heap_block (elem)) >= heap.firstfree) {
  417.     i = index_of_new_heap_block (elem);
  418.     if (i == (size_t) -1)
  419.       fatal ("Out of heap");
  420.   }
  421.  
  422.   heap.total_used += elem;
  423.  
  424.   hb = heap.array[i];
  425.   ret = (void *) (hb->array + hb->firstfree);
  426.   hb->firstfree += elem;
  427.  
  428.   if (i != heap.search_start &&
  429.       hb->size - hb->firstfree < SIZE_MINIMUM) {
  430.     heap.array [i]                   = heap.array [heap.search_start];
  431.     heap.array [heap.search_start++] = hb;
  432.   } else if (hb->size - hb->firstfree < SIZE_MINIMUM)
  433.     heap.search_start++;
  434.  
  435.   return ret;
  436. }
  437.  
  438. static void uncache (void)
  439. {
  440.   struct heap_block *hb;
  441.   size_t i;
  442.  
  443.   if (cached_heap_end != dummy_cache_buf) {
  444.     hb = heap.array [cached_block_no];
  445.     i = hb->firstfree;
  446.     hb->firstfree = cached_heap_top - hb->array;
  447.     heap.total_used += hb->firstfree - i;
  448.     if (cached_block_no != heap.search_start &&
  449.     hb->size - hb->firstfree < SIZE_MINIMUM) {
  450.       heap.array [cached_block_no]     = heap.array [heap.search_start];
  451.       heap.array [heap.search_start++] = hb;
  452.     } else if (hb->size - hb->firstfree < SIZE_MINIMUM)
  453.       heap.search_start++;
  454.   }
  455. }
  456.  
  457. static
  458. void *getbytes (size_t bytes)
  459. {
  460.   size_t elem = (bytes + sizeof (align_t) - 1) / sizeof (align_t);
  461.   size_t i;
  462.   struct heap_block *hb;
  463.   void *ret;
  464.  
  465.   getbytes_count++;
  466.  
  467.   ret = cached_heap_top;
  468.   cached_heap_top += elem;
  469.   if (cached_heap_top <= cached_heap_end)
  470.     return ret;
  471.  
  472.   cached_heap_top -= elem;
  473.   uncache ();
  474.  
  475.   if ((i = index_of_satisfying_heap_block (elem)) >= heap.firstfree)
  476.     if (gc_running || heap.total_size < min_heap_size) {
  477.       i = index_of_new_heap_block (elem);
  478.       if (i == (size_t) -1) {
  479.     if (gc_running)
  480.       fatal ("Out of heap");
  481.     else {
  482.       /* decrease min_heap_size to avoid further warnings */
  483.       min_heap_size /= 2;
  484.       warning ("memory allocation problem causes premature GC");
  485.       goto the_normal_way;
  486.     }
  487.       }
  488.     } else {
  489. the_normal_way:
  490.       garbage_collection ();
  491.       uncache ();        /* necessary due to with-gc-strategy */
  492.       if ((i = index_of_satisfying_heap_block (elem)) >= heap.firstfree)
  493.     i = index_of_new_heap_block (elem);
  494.       if (i == (size_t) -1)
  495.     reset ("Out of heap");
  496.     }
  497.  
  498.   cached_block_no = i;
  499.   hb = heap.array [i];
  500.   cached_heap_top = hb->array + hb->firstfree;
  501.   cached_heap_end = hb->array + hb->size;
  502.  
  503.   ret = cached_heap_top;
  504.   cached_heap_top += elem;
  505.  
  506.   return ret;
  507. }
  508.  
  509. void *getmem (object_descriptor _, size_t bytes)
  510. {
  511.   void *ret;
  512.  
  513.   if (bytes == 0)
  514.     bytes = _->size;
  515.  
  516.   assert (bytes > 0);
  517.  
  518.   /* make sure to allocate enough space for storing broken hearts */
  519.   if (bytes < sizeof (struct broken_heart))
  520.     bytes = sizeof (struct broken_heart);
  521.  
  522.   ret = getbytes (bytes);
  523.  
  524.   /* set everything to zero */
  525.   memset (ret, 0, bytes);
  526.  
  527.   /* insert object_descriptor */
  528.   ((struct broken_heart *)ret)->_ = _;
  529.  
  530.   return ret;
  531. }
  532.  
  533. /*
  534.  * Implementation of dump and restore
  535.  */
  536.  
  537. static void recur_dump_ul (unsigned long l, FILE *file)
  538. {
  539.   if (l != 0) {
  540.     recur_dump_ul (l / 0400, file);
  541.     putc (l % 0400, file);
  542.   }
  543. }
  544.  
  545. void dump_ul (unsigned long l, FILE *file)
  546. {
  547.   int i;
  548.   unsigned long tmp;
  549.  
  550.   for (tmp = l, i = 0; tmp != 0; tmp /= 0400, i++);
  551.   putc (i, file);
  552.   recur_dump_ul (l, file);
  553. }
  554.  
  555. unsigned long restore_ul (FILE *file)
  556. {
  557.   int i, tmp;
  558.   unsigned long l;
  559.  
  560.   if ((i = getc (file)) == EOF)
  561. eof:
  562.     fatal ("bad dump file format");
  563.   l = 0;
  564.   while (i-- > 0) {
  565.     if ((tmp = getc (file)) == EOF)
  566.       goto eof;
  567.     l = l * 0400 + (tmp & 0377);
  568.   }
  569.   return l;
  570. }
  571.  
  572. # define HASH_SIZE 37
  573. /* In fact, that's not tunable, because portability of dumps depends on it */
  574.  
  575. # define refer_tag(x) ((unsigned long)(x))
  576. # define hash_tag(x) (refer_tag(x)%HASH_SIZE)
  577.  
  578. static
  579. unsigned long again_count[HASH_SIZE];
  580.  
  581. static
  582. struct loctab_entry {
  583.   unsigned long tag;
  584.   void *location;
  585. } *location_table[HASH_SIZE];
  586.  
  587. /*ARGSUSED*/
  588. static
  589. void do_struct_analysis (void **object_ptr, void *ignore)
  590. {
  591.   struct broken_heart *obj = *object_ptr;
  592.   object_descriptor current;
  593.  
  594.   if (obj == NULL)
  595.     return;
  596.   current = obj->_;
  597.   if (current->size == 0 && current->size_hook == NULL)
  598.     return;
  599.   switch (current->kind) {
  600.   case OD_NORMAL:
  601.     obj->_ = ¤t->whole_vector[OD_MARKED];
  602.     if (current->for_each_sub != NULL)
  603.       (* current->for_each_sub) (obj, do_struct_analysis, NULL);
  604.     break;
  605.   case OD_MARKED:
  606.     obj->_ = ¤t->whole_vector[OD_AGAIN];
  607.     ++again_count[hash_tag(obj)];
  608.     break;
  609.   }
  610. }
  611.  
  612. static
  613. void structure_analysis (void)
  614. {
  615.   int i;
  616.   perform_on_subs_proc fesp;
  617.  
  618.   for (i = 0; i < gva_firstfree; i++)
  619.     if ((fesp = gva [i].for_each_sub) != NULL)
  620.       (* fesp) (gva [i].location, do_struct_analysis, NULL);
  621.     else
  622.       do_struct_analysis (gva [i].location, NULL);
  623. }
  624.  
  625. /*ARGSUSED*/
  626. static
  627. void do_cleanup (void **object_ptr, void *ignore)
  628. {
  629.   struct broken_heart *obj = *object_ptr;
  630.   object_descriptor current;
  631.  
  632.   if (obj == NULL)
  633.     return;
  634.   current = obj->_;
  635.   if (current->kind != OD_NORMAL) {
  636.     obj->_ = ¤t->whole_vector[OD_NORMAL];
  637.     if (current->for_each_sub != NULL)
  638.       (* current->for_each_sub) (obj, do_cleanup, NULL);
  639.   }
  640. }
  641.  
  642. static
  643. void cleanup (void)
  644. {
  645.   int i;
  646.   perform_on_subs_proc fesp;
  647.  
  648.   for (i = 0; i < gva_firstfree; i++)
  649.     if ((fesp = gva [i].for_each_sub) != NULL)
  650.       (* fesp) (gva [i].location, do_cleanup, NULL);
  651.     else
  652.       do_cleanup (gva [i].location, NULL);
  653. }
  654.  
  655. /*ARGSUSED*/
  656. static
  657. void object_dump (void **object_ptr, void *vfile)
  658. {
  659.   struct broken_heart *obj = *object_ptr;
  660.   FILE *file = (FILE *) vfile;
  661.   object_descriptor od;
  662.   perform_on_subs_proc fesp;
  663.  
  664.   if (obj == NULL) {
  665.     putc (NULL_IDENTIFIER, file);
  666.     return;
  667.   }
  668.   od = obj->_;
  669.   switch (od->kind) {
  670.   case OD_AGAIN:
  671.     obj->_ = &od->whole_vector[OD_WRITTEN];
  672.     putc (MARK_IDENTIFIER, file);
  673.     dump_ul (refer_tag(obj), file);
  674.     /* here is flow between cases, this is not an error! */
  675.   case OD_MARKED:
  676.     putc (od->identifier, file);
  677.     if (od->dump != NULL)
  678.       (* od->dump) (obj, file);
  679.     if ((fesp = od->for_each_sub) != NULL)
  680.       (* fesp) (obj, object_dump, vfile);
  681.     break;
  682.   case OD_NORMAL:
  683.     assert (od->size == 0 && od->size_hook == 0);
  684.     putc (od->identifier, file);
  685.     if (od->dump != NULL)
  686.       (* od->dump) (obj, file);
  687.     break;
  688.   default: /* OD_WRITTEN */
  689.     putc (REFERTO_IDENTIFIER, file);
  690.     dump_ul (refer_tag(obj), file);
  691.     break;
  692.   }
  693. }
  694.  
  695. static
  696. void dump (FILE *file)
  697. {
  698.   int i;
  699.   perform_on_subs_proc fesp;
  700.  
  701.   for (i = 0; i < gva_firstfree; i++)
  702.     if ((fesp = gva [i].for_each_sub) != NULL)
  703.       (* fesp) (gva [i].location, object_dump, (void *)file);
  704.     else
  705.       object_dump (gva [i].location, (void *)file);
  706. }
  707.  
  708. void dump_storage (FILE *file)
  709. {
  710.   int i;
  711.  
  712.   assert (sizeof (void *) <= sizeof (unsigned long));
  713.  
  714.   for (i = 0; i < HASH_SIZE; i++)
  715.     again_count[i] = 0;
  716.   structure_analysis ();
  717.   for (i = 0; i < HASH_SIZE; i++)
  718.     dump_ul (again_count[i], file);
  719.   dump (file);
  720.   cleanup ();
  721. }
  722.  
  723. static
  724. void init_location_table (FILE *file)
  725. {
  726.   int i;
  727.   unsigned long tmp;
  728.  
  729.   for (i = 0; i < HASH_SIZE; i++) {
  730.     again_count[i] = 0;
  731.     tmp = restore_ul (file);
  732.     if (tmp != 0)
  733.       if ((location_table[i] = (struct loctab_entry *)
  734.         malloc (tmp * sizeof (struct loctab_entry))) == NULL)
  735.     fatal ("ran out ouf space");
  736.   }
  737. }
  738.  
  739. static
  740. void free_location_table (void)
  741. {
  742.   int i;
  743.  
  744.   for (i = 0; i < HASH_SIZE; i++)
  745.     free (location_table[i]);
  746. }
  747.  
  748. static
  749. void register_location (unsigned long tag, void *location)
  750. {
  751.   int index;
  752.   struct loctab_entry *ep;
  753.  
  754.   index = hash_tag (tag);
  755.   ep = location_table[index] + again_count[index]++;
  756.   ep->tag = tag;
  757.   ep->location = location;
  758. }
  759.  
  760. static
  761. void *lookup_location (unsigned long tag)
  762. {
  763.   int index;
  764.   struct loctab_entry *ep, *last;
  765.  
  766.   index = hash_tag (tag);
  767.   last = (ep = location_table[index]) + again_count[index];
  768.   while (ep < last)
  769.     if (ep->tag == tag)
  770.       return ep->location;
  771.     else
  772.       ep++;
  773.   fatal ("bad dump file format");
  774.   /*NOTREACHED*/
  775. }
  776.  
  777. static
  778. void restore_object (void **object_ptr, void *vfile)
  779. {
  780.   FILE *file = (FILE *) vfile;
  781.   int identifier;
  782.   unsigned long tag = 0;    /* to shut up the compiler */
  783.   int marked;
  784.   void *location;
  785.   object_descriptor od;
  786.  
  787.   marked = 0;
  788.   switch (identifier = getc (file)) {
  789.   case EOF:
  790. eof:
  791.     fatal ("bad dump file format");
  792.     break;
  793.   case NULL_IDENTIFIER:
  794.     *object_ptr = NULL;
  795.     break;
  796.   case REFERTO_IDENTIFIER:
  797.     tag = restore_ul (file);
  798.     *object_ptr = lookup_location (tag);
  799.     break;
  800.   case MARK_IDENTIFIER:
  801.     marked = 1;
  802.     tag = restore_ul (file);
  803.     if ((identifier = getc (file)) == EOF)
  804.       goto eof;
  805.   default:
  806.     od = identifier_map[identifier];
  807.     if (od->restore_init == NULL) {
  808.       assert (od->size > 0);
  809.       location = new (od);
  810.     } else {
  811.       location = (*od->restore_init) (file);
  812.       assert (((struct broken_heart *)location)->_ == od);
  813.     }
  814.     *object_ptr = location;
  815.     if (marked)
  816.       register_location (tag, location);
  817.     if (od->for_each_sub != NULL)
  818.       (*od->for_each_sub) (location, restore_object, vfile);
  819.     if (od->restore_finish != NULL)
  820.       (*od->restore_finish) (location);
  821.     break;
  822.   }
  823. }
  824.  
  825. void restore_storage (FILE *file)
  826. {
  827.   int i;
  828.   perform_on_subs_proc fesp;
  829.  
  830.   /* prevent gc from running (otherwise location table gets corrupted) */
  831.   gc_running = 1;
  832.   /* use passive heap */
  833.   exchange_heaps ();
  834.   init_location_table (file);
  835.   for (i = 0; i < gva_firstfree; i++)
  836.     if ((fesp = gva [i].for_each_sub) != NULL)
  837.       (* fesp) (gva [i].location, restore_object, (void *)file);
  838.     else
  839.       restore_object (gva [i].location, (void *)file);
  840.   free_location_table ();
  841.   /* reset gc_running flag */
  842.   gc_running = 0;
  843. }
  844.  
  845. void *new_location_of (void *obj)
  846. {
  847.   if (((struct broken_heart *) obj)->_ == &broken_heart_description)
  848.     return ((struct broken_heart *) obj)->new_location;
  849.   return obj;
  850. }
  851.  
  852. /*
  853.  * Module initialization
  854.  */
  855.  
  856. void init_all_modules (void)
  857. {
  858.   all_modules (MODULE_INIT);
  859. }
  860.